package medium

import (
	. "GoLeetcode/common"
)

/*
时间复杂度:O(N)
空间复杂度:O(N)

层序遍历
*/

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findBottomLeftValue(root *TreeNode) int {
	var ans int
	level := []*TreeNode{root}
	for len(level) != 0 {
		ans = level[0].Val
		pos := len(level)
		for _, node := range level {
			if node != nil {
				if node.Left != nil {
					level = append(level, node.Left)
				}
				if node.Right != nil {
					level = append(level, node.Right)
				}
			}
		}
		level = level[pos:]
	}
	return ans
}